package com.jack.leetcode.eachproblem_2020;

public class 单词搜索 {

    private int[][] dir = {{1, 0},{-1, 0},{0, -1},{0, 1}};
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        boolean[][] flag = new boolean[m][n];
        return dfs(flag, board, word, 0, 0, 0);
    }

    private boolean dfs(boolean[][] flag, char[][] board, String word, int index, int begin, int end){
        if(index == word.length()){
            return true;
        }
        char c = word.charAt(index);
        if(index == 0){
            for(int i = 0;i < board.length;i++){
                for(int j = 0;j < board[0].length;j++){
                    if(c == board[i][j] && !flag[i][j]){
                        flag[i][j] = true;
                        if(dfs(flag, board, word, index + 1, i, j)){
                            return true;
                        }
                        flag[i][j] = false;
                    }
                }
            }
        }else{
            for (int[] ints : dir) {
                int newBegin = begin + ints[0];
                int newEnd = end + ints[1];
                boolean isValid = newBegin >= 0 && newBegin < board.length
                        && newEnd >= 0 && newEnd < board[0].length
                        && c == board[newBegin][newEnd] && !flag[newBegin][newEnd];
                if(isValid){
                    flag[newBegin][newEnd] = true;
                    if(dfs(flag, board, word, index + 1, newBegin, newEnd)){
                        return true;
                    }
                    flag[newBegin][newEnd] = false;
                }
            }
        }
        return false;
    }
}
